package 简单.数学;

import java.util.Arrays;

/**
 * 统计所有小于非负整数 n 的质数的数量。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 10
 * 输出：4
 * 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 * <p>
 * 来源：https://leetcode-cn.com/problems/count-primes/
 */
public class 计数质数_204 {

    public static void main(String[] args) {

        System.out.println(countPrimes(100));

    }

    //如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x一定不是质数
    //如果 x 是合数，那么<x的数字已经将x标记为合数了
    public static int countPrimes(int n) {
        int[] isPrime = new int[n];
        //1不是质数
        if (n == 0 || n == 1) {
            return 0;
        }
        int count = 0;
        //默认全是质数
        Arrays.fill(isPrime, 1);
        for (int i = 2; i < n; i++) {
            //如果i为合数，那么i的因子是之前一定存在一个数y，遍历到y的时候，一定将i设置为0了
            if (isPrime[i] == 1) {
                count++;
                //直接从 x*x 开始标记，因为 2x,3x,… 这些数一定在 x*x 之前就被其他数的倍数标记过了
                //2*3，2*4，... 3*3,3*4，...
                for (int j = i; (long) i * j < n; j++) {
                    isPrime[i * j] = 0;
                }
            }
        }
        return count;
    }

}
